#define _CRT_SECURE_NO_WARNINGS 1


#include<stdio.h>


struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    
};
//void preorder(struct TreeNode* root, int* array, int* pi)
//{
//    if (root == NULL)
//        return;
//    array[*pi] = root->val;
//    (*pi)++;
//    preorder(root->left, array, pi);
//    preorder(root->right, array, pi);
//
//}
//
//int TreeSize(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//    int n = TreeSize(root);
//    int* array = (int*)malloc(sizeof(int) * n);
//    int i = 0;
//
//    *returnSize = n;
//    preorder(root, array, &i);
//    return array;
//}


//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//
//    if (root->left && root->val != root->left->val)
//    {
//        return false;
//    }
//    if (root->right && root->val != root->right->val)
//    {
//        return false;
//    }
//
//    return isUnivalTree(root->left)
//        && isUnivalTree(root->right);
//}

//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return 0;
//    }
//
//    int lr = maxDepth(root->left);
//    int rr = maxDepth(root->right);
//
//    return lr > rr ? lr + 1 : rr + 1;
//}

//struct TreeNode* invertTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return NULL;
//    }
//    struct TreeNode* temp;
//
//
//    if (root->left || root->right)
//    {
//        struct TreeNode* lt = root->left;
//        temp = lt;
//        root->left = root->right;
//        root->right = temp;
//        invertTree(root->left);
//        invertTree(root->right);
//    }
//    return root;
//
//}

//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//    {
//        return true;
//    }
//    if (p == NULL || q == NULL)
//    {
//        return false;
//    }
//
//    if (p->val != q->val)
//    {
//        return false;
//    }
//    return isSameTree(p->left, q->left)
//        && isSameTree(p->right, q->right);
//}

//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//    {
//        return true;
//    }
//    if (p == NULL || q == NULL)
//    {
//        return false;
//    }
//
//    if (p->val != q->val)
//    {
//        return false;
//    }
//    return isSameTree(p->left, q->left)
//        && isSameTree(p->right, q->right);
//}
//
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//
//    if (root == NULL)
//    {
//        return false;
//    }
//    if (isSameTree(root, subRoot))
//    {
//        return true;
//    }
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}

//int TreeHight(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    int lt = TreeHight(root->left);
//    int rt = TreeHight(root->right);
//    return lt > rt ? lt + 1 : rt + 1;
//}
//bool isBalanced(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//
//    return fabs(TreeHight(root->left) - TreeHight(root->right)) <= 1
//        && isBalanced(root->left) && isBalanced(root->right);
//}